package code.daily;

import java.util.*;

/**
 * @author 26029
 * @date 2025/4/24
 * @description 每日一题
 */
public class DailyTemp {
    // 1399. 统计最大组的数目 4-23 easy
    public int countLargestGroup(int n) {
        // 1 <= n <= 10^4
        int[] count = new int[37];
        int max = 0;
        int maxNum = 0;
        for (int i = 1; i <= n; i++) {
            int digitSum = getDigitSum(i);
            count[digitSum]++;
            if (count[digitSum] > max) {
                max = count[digitSum];
                maxNum = 1;
            } else if (count[digitSum] == max) {
                maxNum++;
            }
        }
        return maxNum;
    }

    private int getDigitSum(int a) {
        int ans = 0;
        while (a > 0) {
            ans += a % 10;
            a /= 10;
        }
        return ans;
    }

    // 2799. 统计完全子数组的数目 4-24 mid
    public int countCompleteSubarrays(int[] nums) {
        // 滑动窗口
        int n = nums.length;
        // 找到不同数字的数量
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        int diff_num = set.size();
        // map记录当前数字在滑动窗口中出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        int ans = 0;
        while (right < n) {
            int num = nums[right];
            map.put(num, map.getOrDefault(num, 0) + 1);
            // 如果当前是满的，left指针右移
            if (map.size() == diff_num) {
                while (map.get(nums[left]) >= 2) {
                    map.put(nums[left], map.get(nums[left]) - 1);
                    left++;
                }
                ans += left + 1;
            }
            right++;
        }
        return ans;
    }

    // 2845. 统计趣味子数组的数目 4-25 mid
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        // 数学推导
        Map<Integer, Long> freq = new HashMap<>(); // key：抽象的数学推导式 value：满足的个数
        freq.put(0, 1L); // 初始前缀和为0

        long ans = 0;
        int prefix = 0; // 前缀和，表示[0, i]这 i + 1 个元素有多少个是满足条件的

        // 推导：
        //      (prefix[r] - prefix[l-1]) % modulo == k 表示[l, r]满足条件
        // 移项：
        //      prefix[r] % modulo == (prefix[l-1] + k) % modulo
        // 把k移过去，故，对于一个r，我们希望找到所有的l-1，满足：
        //      prefix[l-1] % modulo == (prefix[r] - k + modulo) % modulo
        // 右面这个 (prefix[r] - k + modulo) % modulo 作为key，找map里value，加到ans上
        for (int num : nums) {
            // 判断是否符合条件
            if (num % modulo == k)
                prefix++;

            int key = (prefix - k + modulo) % modulo;
            ans += freq.getOrDefault(key, 0L);

            int newKey = prefix % modulo;
            freq.put(newKey, freq.getOrDefault(newKey, 0L) + 1);
        }

        return ans;
    }

    // 2444. 统计定界子数组的数目 4-26 hard
    public long countSubarrays(int[] nums, int minK, int maxK) {
        int len = nums.length;
        List<int[]> list = new ArrayList<>();
        int nowMax = 0, nowMin = Integer.MAX_VALUE;
        for (int right = 0, left = 0; right < len; right++) {
            // 如果超过了
            if (nums[right] < minK || nums[right] > maxK) {
                // 如果符合条件，加上
                if (right > left && nowMax == maxK && nowMin == minK)
                    list.add(new int[]{left, right - 1});
                left = right + 1;
                nowMin = Integer.MAX_VALUE;
                nowMax = 0;
            }
            // 没超过，到头了
            else if (right == len - 1) {
                nowMin = Math.min(nowMin, nums[right]);
                nowMax = Math.max(nowMax, nums[right]);
                // 如果符合条件,加上
                if (nowMax == maxK && nowMin == minK)
                    list.add(new int[]{left, right});
            }
            // 正常加上
            else {
                nowMin = Math.min(nowMin, nums[right]);
                nowMax = Math.max(nowMax, nums[right]);
            }
        }
        // 得到了分段的List<int[]>，处理每个int[]，用滑动窗口
        long ans = 0;
        for (int[] pos : list) {
            int l = pos[0], r = pos[1];
            int left = l, right = l;
            int maxNum = 0, minNum = 0;
            while (right <= r) {
                if (nums[right] == maxK)
                    maxNum++;
                if (nums[right] == minK)
                    minNum++;
                // 如果当前满足答案，加上[left, right], [left, right + 1], ..., [left, r]作为答案，同时left++
                while (maxNum > 0 && minNum > 0) {
                    ans += r - right + 1;
                    if (nums[left] == maxK)
                        maxNum--;
                    if (nums[left] == minK)
                        minNum--;
                    left++;
                }
                right++;
            }
        }
        return ans;
    }

    // 3392. 统计符合条件长度为 3 的子数组数目 4-27 easy
    public int countSubarrays(int[] nums) {
        int len = nums.length;
        int ans = 0;
        for (int i = 2; i < len; i++) {
            int n1 = nums[i - 2], n2 = nums[i - 1], n3 = nums[i];
            if ((n1 + n3) * 2 == n2)
                ans++;
        }
        return ans;
    }

    // 2302. 统计得分小于 K 的子数组数目 4-28 hard
    public long countSubarrays(int[] nums, long k) {
        int len = nums.length;
        long ans = 0;
        int left = 0, right = 0;
        long nowSum = 0;
        while (right < len) {
            int num = nums[right];
            nowSum += num;
            long nowAns = nowSum * (right - left + 1);
            // 如果当前[left, right]的答案>=k 则left++
            while (left <= right && nowAns >= k) {
                nowSum -= nums[left];
                left++;
                nowAns = nowSum * (right - left + 1);
            }
            // 如果当前[left, right]的答案<k 则ans += {以right结尾，以left、left+1、...、right开头的答案}
            ans += right - left + 1;
            right++;
        }
        return ans;
    }

    // 2962. 统计最大元素出现至少 K 次的子数组 4-29 mid
    public long countSubarrays(int[] nums, int k) {
        // 得到最大元素
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
        }
        // 滑动窗口
        int left = 0, right = 0;
        int len = nums.length;
        int maxNum = 0;
        long ans = 0;
        while (right < len) {
            if (nums[right] == max)
                maxNum++;
            while (maxNum == k) {
                ans += len - right;
                if (nums[left] == max)
                    maxNum--;
                left++;
            }
            right++;
        }
        return ans;
    }

    // 1295. 统计位数为偶数的数字 4-30 easy
    public int findNumbers(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            int digits = 0; // 唯一的特殊情况，0的数位是1，但是不是偶数个，所以不影响答案
            while (num > 0) {
                num /= 10;
                digits++;
            }
            if (digits % 2 ==0)
                ans++;
        }
        return ans;
    }

    // 2311. 小于等于 K 的最长二进制子序列 6-26 mid
    public int longestSubsequence(String s, int k) {
        long val = 0;
        int count = 0;
        int power = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                count++;
            } else {
                if (power < 32 && val + (1L << count) <= k) {
                    val += (1L << count);
                    count++;
                }
            }
            if (power < 32) power++;
        }
        return count;
    }

    public static void main(String[] args) {

    }
}
